package src.BlueBridge.DeepRecursion;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 */

public class _6全排列 {
    public static void main(String[] args) {
        String A = "abc";
        ArrayList<String> target = getPermutation2(A);
        System.out.println(getPermutation2(A));
        System.out.println(target);
    }

    // 逐步生成法
    public static ArrayList<String> getPermutation1(String A) {
        // 获取字符串长度
        int n = A.length();
        ArrayList<String> res = new ArrayList<>();
        // 初始化，包含第一个字符
        res.add(A.charAt(0) + "");
        // 后面的每个字符插入到前面生成集合的每个元素里面
        for (int i = 1 ; i < n ; i++) {
            ArrayList<String> res_new = new ArrayList<>();
            // 新字符
            char c = A.charAt(i);
            // 访问上一层集合中的每个字符串
            for (String str : res) {
                // 插入到每个位置，形成一个新串
                // 加在前面
                String newStr = c + str;
                res_new.add(newStr);
                // 加在后面
                newStr = str + c;
                res_new.add(newStr);
                // 加在中间
                for (int j = 1 ; j < str.length() ; j++) {
                    newStr = str.substring(0, j) + c + str.substring(j);
                    res_new.add(newStr);
                }
            }
            // 更新
            res = res_new;
        }
        return res;
    }

    // 递归回溯法
    static ArrayList<String> res = new ArrayList<>();
    public static ArrayList<String> getPermutation2(String A) {
        char[] arr = A.toCharArray();
        Arrays.sort(arr); // abcd
        getPermutation2Core(arr, 0);
        return res;
    }
    public static void getPermutation2Core(char[] arr, int k) {
        if (k == arr.length) {
            res.add(new String(arr));
        }
        // 从k位开始的每个字符，都尝试放在重新排列的k这个位置
        for (int i = k ; i < arr.length ; i++) {
            // 把后面的每个字符换到k位
            swap(arr, i, k);
            getPermutation2Core(arr, k + 1);
            // 回溯
            swap(arr, i, k);
        }
    }
    public static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
